{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Confusing Number II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: confusingNumberII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #易混淆数 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>易混淆数</strong>（Confusing Number）指的是一个数字在整体旋转 <code>180°</code> 以后，能够得到一个和原来&nbsp;<strong>不同&nbsp;</strong>的数，且 <strong>新数字的每一位都应该是有效的</strong>。</p>\n",
    "\n",
    "<p>本题我们会将数字旋转 <code>180°</code> 来生成一个新的数字。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>当 <code>0、1、6、8、9</code> 旋转 <code>180°</code> 以后，我们得到的新数字分别为&nbsp;0、1、9、8、6。</li>\n",
    "\t<li>当&nbsp;<code>2、3、4、5、7</code> 旋转 <code>180°</code> 后，是 <strong>无法</strong> 得到任何数字的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请注意，在旋转一个数字之后，我们可以忽略前导零。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，在旋转 <code>8000</code> 之后，我们有 <code>0008</code> ，它被认为只是 <code>8</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给出正整数&nbsp;<code>n</code>，请你返回&nbsp;&nbsp;<em><code>[1, n]</code>&nbsp;范围内的 <strong>易混淆数</strong> 的数量&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 20\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>易混淆数为 [6,9,10,16,18,19]。\n",
    "6 转换为 9\n",
    "9 转换为 6\n",
    "10 转换为 01 也就是 1\n",
    "16 转换为 91\n",
    "18 转换为 81\n",
    "19 转换为 61\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 100\n",
    "<strong>输出：</strong>19\n",
    "<strong>解释：</strong>易混淆数为 [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [confusing-number-ii](https://leetcode.cn/problems/confusing-number-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [confusing-number-ii](https://leetcode.cn/problems/confusing-number-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['20', '100']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        m = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}\n",
    "\n",
    "        def f(i: int, pre: str, is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s):\n",
    "                if not is_num:\n",
    "                    return 0\n",
    "                rev = ''.join(m[letter] for letter in reversed(pre))\n",
    "                return 0 if pre == rev else 1\n",
    "            count = 0\n",
    "            if not is_num:\n",
    "                count = f(i + 1, pre, False, False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in [0, 1, 6, 8, 9]:\n",
    "                if low <= d <= up:\n",
    "                    count += f(i + 1, pre + str(d), is_limit and d == up, True)\n",
    "            return count\n",
    "\n",
    "        return f(0, '', True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        valid = [0, 1, 6, 8, 9]\n",
    "        mapping = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}\n",
    "\n",
    "        self.count = 0\n",
    "\n",
    "        def backtrack(v, rotation, digit):\n",
    "            if v != rotation: self.count += 1  \n",
    "            for i in valid: \n",
    "                if v * 10 + i > n: break \n",
    "                else: backtrack(v * 10 + i, mapping[i] * digit + rotation, digit * 10)\n",
    "        \n",
    "        for x in valid[1:]: backtrack(x, mapping[x], 10)\n",
    "\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        valid = [0, 1, 6, 8, 9]\n",
    "        mapping = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}\n",
    "\n",
    "        self.count = 0\n",
    "\n",
    "        def backtrack(v, rotation, digit):\n",
    "            if v != rotation: self.count += 1  \n",
    "            for i in valid: \n",
    "                if v * 10 + i > n: break \n",
    "                else: backtrack(v * 10 + i, mapping[i] * digit + rotation, digit * 10)\n",
    "        \n",
    "        backtrack(1, 1, 10)\n",
    "        backtrack(6, 9, 10)\n",
    "        backtrack(8, 8, 10)\n",
    "        backtrack(9, 6, 10)\n",
    "\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        dic={'0':'0','1':'1','6':'9','9':'6','8':'8'}\n",
    "        string=str(n)\n",
    "      \n",
    "        def dfs(i,ss,sp,islimit,isnum):\n",
    "            if i==len(string):\n",
    "                if isnum and ss!=sp[::-1]:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res=0\n",
    "            if not isnum:\n",
    "                res+=dfs(i+1,ss,sp,False,False)\n",
    "            low=0 if isnum else 1\n",
    "            up=int(string[i]) if islimit else 9\n",
    "            for j in range(low,up+1):\n",
    "                if str(j) in dic.keys():\n",
    "                    res+=dfs(i+1,ss+str(j),sp+dic[str(j)],islimit and j==up,True)\n",
    "            return res\n",
    "        return dfs(0,\"\",\"\",True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        dic={'0':'0','1':'1','6':'9','9':'6','8':'8'}\n",
    "        string=str(n)\n",
    "      \n",
    "        def dfs(i,ss,sp,islimit,isnum):\n",
    "            if i==len(string):\n",
    "                if isnum and ss!=sp[::-1]:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res=0\n",
    "            if not isnum:\n",
    "                res+=dfs(i+1,ss,sp,False,False)\n",
    "            low=0 if isnum else 1\n",
    "            up=int(string[i]) if islimit else 9\n",
    "            for j in range(low,up+1):\n",
    "                if str(j) in dic.keys():\n",
    "                    res+=dfs(i+1,ss+str(j),sp+dic[str(j)],islimit and j==up,True)\n",
    "            return res\n",
    "        return dfs(0,\"\",\"\",True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        dic={'0':'0','1':'1','6':'9','9':'6','8':'8'}\n",
    "        string=str(n)\n",
    "      \n",
    "        def dfs(i,ss,sp,islimit,isnum):\n",
    "            if i==len(string):\n",
    "                if isnum and ss!=sp[::-1]:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res=0\n",
    "            if not isnum:\n",
    "                res+=dfs(i+1,ss,sp,False,False)\n",
    "            low=0 if isnum else 1\n",
    "            up=int(string[i]) if islimit else 9\n",
    "            for j in range(low,up+1):\n",
    "                if str(j) in dic.keys():\n",
    "                    res+=dfs(i+1,ss+str(j),sp+dic[str(j)],islimit and j==up,True)\n",
    "            return res\n",
    "        return dfs(0,\"\",\"\",True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        confuse_nums = [0, 1, 6, 8, 9]\n",
    "        dct = {\"0\": \"0\", \"1\": \"1\", \"6\": \"9\", \"8\": \"8\", \"9\": \"6\"}\n",
    "        s = str(n)\n",
    "\n",
    "        def check(st):\n",
    "            if int(st) != int(\"\".join(dct[t] for t in st)[::-1]):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        \n",
    "        def helper(i, pre, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num and check(pre))\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += helper(i + 1, \"\", False, False)\n",
    "            lower = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in confuse_nums:\n",
    "                if lower <= d <= up:\n",
    "                    res += helper(i+1, pre+str(d),is_limit and d == up, True)\n",
    "            return res\n",
    "        \n",
    "        return helper(0, \"\", True, False)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        valid = [0, 1, 6, 8, 9]\n",
    "        mapping = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}\n",
    "\n",
    "        self.count = 0\n",
    "\n",
    "        def backtrack(v, rotation, digit):\n",
    "            # if v: \n",
    "            if v != rotation: \n",
    "                self.count += 1  \n",
    "            for i in valid: \n",
    "                if v * 10 + i > n:\n",
    "                    break \n",
    "                else:\n",
    "                    backtrack(v * 10 + i, mapping[i] * digit + rotation, digit * 10)\n",
    "        \n",
    "        backtrack(1, 1, 10)\n",
    "        backtrack(6, 9, 10)\n",
    "        backtrack(8, 8, 10)\n",
    "        backtrack(9, 6, 10)\n",
    "\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        mp = {0:0,1:1,6:9,8:8,9:6}\n",
    "\n",
    "        s = str(n)\n",
    "\n",
    "        # @cache\n",
    "        def dfs(i,cur, is_limit):\n",
    "            if i == len(s):\n",
    "                cur = str(int(cur))\n",
    "                res = ''\n",
    "                for c in cur:\n",
    "                    if int(c) not in mp.keys():\n",
    "                        return 0\n",
    "                    res += str(mp[int(c)])\n",
    "                res = res[::-1]\n",
    "                # print(cur,res)\n",
    "                return int(cur != res)\n",
    "            low = 0\n",
    "            up = 9 if not is_limit else int(s[i])\n",
    "            ans = 0\n",
    "            for d in range(low, up+1):\n",
    "                if d not in mp.keys():\n",
    "                    continue\n",
    "                ans += dfs(i+1,cur+str(d),is_limit and d==up)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,'',True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        mp = {'0':'0','1':'1','6':'9','8':'8','9':'6'}\n",
    "\n",
    "        s = str(n)\n",
    "\n",
    "        # @cache\n",
    "        def dfs(i, cur, is_limit):\n",
    "            if i == len(s):\n",
    "                cur = str(int(cur))\n",
    "                res = ''\n",
    "                for c in cur:\n",
    "                    if c not in mp.keys():\n",
    "                        return 0\n",
    "                    res += mp[c]\n",
    "                res = res[::-1]\n",
    "                # print(cur,res)\n",
    "                return int(cur != res)\n",
    "            low = 0\n",
    "            up = 9 if not is_limit else int(s[i])\n",
    "            ans = 0\n",
    "            for d in range(low, up+1):\n",
    "                if str(d) not in mp.keys():\n",
    "                    continue\n",
    "                ans += dfs(i+1,cur+str(d),is_limit and d==up)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,'',True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        valid = [0,1,6,8,9]\n",
    "        mapping = {0: 0,1: 1,6: 9,8: 8, 9: 6}\n",
    "\n",
    "        self.count = 0\n",
    "\n",
    "        def backtrack(v, rotation, digit):\n",
    "            if v: \n",
    "                if v != rotation: \n",
    "                    self.count += 1  \n",
    "            for i in valid: \n",
    "                if v * 10 + i > n:\n",
    "                    break \n",
    "                else:\n",
    "                    backtrack(v * 10 + i, mapping[i]*digit + rotation, digit*10)\n",
    "        \n",
    "        backtrack(1, 1, 10)\n",
    "        backtrack(6, 9, 10)\n",
    "        backtrack(8, 8, 10)\n",
    "        backtrack(9, 6, 10)\n",
    "\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        confuse_nums = [0, 1, 6, 8, 9]\n",
    "        dct = {\"0\": \"0\", \"1\": \"1\", \"6\": \"9\", \"8\": \"8\", \"9\": \"6\"}\n",
    "        s = str(n)\n",
    "\n",
    "        def check(st):\n",
    "            if int(st) != int(\"\".join(dct[t] for t in st)[::-1]):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        \n",
    "        def helper(i, pre, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num and check(pre))\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += helper(i + 1, \"\", False, False)\n",
    "            lower = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in confuse_nums:\n",
    "                if lower <= d <= up:\n",
    "                    res += helper(i+1, pre+str(d),is_limit and d == up, True)\n",
    "            return res\n",
    "        \n",
    "        return helper(0, \"\", True, False)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        valid = [0, 1, 6, 8, 9]\n",
    "        mapping = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}\n",
    "\n",
    "        self.count = 0\n",
    "\n",
    "        def backtrack(v, rotation, digit):\n",
    "            if v: \n",
    "                if v != rotation: \n",
    "                    self.count += 1  \n",
    "            for i in valid: \n",
    "                if v * 10 + i > n:\n",
    "                    break \n",
    "                else:\n",
    "                    backtrack(v * 10 + i, mapping[i] * digit + rotation, digit * 10)\n",
    "        \n",
    "        backtrack(1, 1, 10)\n",
    "        backtrack(6, 9, 10)\n",
    "        backtrack(8, 8, 10)\n",
    "        backtrack(9, 6, 10)\n",
    "\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        nums = [0, 1, 6, 8, 9]\n",
    "        length = len(str(n))\n",
    "\n",
    "        def count(n, d):\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            total = 5 ** (d - 1) - 1\n",
    "            high = n // 10 ** (d - 1)\n",
    "            for j in nums[1:]:\n",
    "                if j < high:\n",
    "                    total += 5 ** (d - 1)\n",
    "                elif j == high:\n",
    "                    total += count(n % 10 ** (d - 1), d - 1) + 1\n",
    "                else:\n",
    "                    break\n",
    "            return total\n",
    "        \n",
    "        total = count(n, length)\n",
    "\n",
    "        def generate(d):\n",
    "            if d == 1:\n",
    "                return [0, 1, 8]\n",
    "            elif d == 2:\n",
    "                return [0, 11, 69, 88, 96]\n",
    "            pairs = [(0, 0), (1, 1), (6, 9), (8, 8), (9, 6)]\n",
    "            pre = generate(d - 2)\n",
    "            lower = 10 ** (d - 1)\n",
    "            res = []\n",
    "            for l, r in pairs:\n",
    "                for p in pre:\n",
    "                    p = p * 10 + r + l * lower\n",
    "                    res.append(p)\n",
    "            return res\n",
    "        \n",
    "        for d in range(1, length + 1):\n",
    "            lower = 10 ** (d - 1)\n",
    "            for num in generate(d):\n",
    "                if num <= n:\n",
    "                    if num >= lower:\n",
    "                        total -= 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        num = str(n)\n",
    "        test = [int(i) for i in num]\n",
    "\n",
    "        easy = {1 : 2,\n",
    "                2 : 4 * 5 - 4,\n",
    "                3 : 4 * 5 * 5 - 4 * 3,\n",
    "                4 : 4 * (5 ** 3) - 4 * 5,\n",
    "                5 : 4 * (5 ** 4) - 4 * 5 * 3,\n",
    "                6 : 4 * (5 ** 5) - 4 * 5 * 5,\n",
    "                7 : 4 * (5 ** 6) - 4 * 5 * 5 * 3,\n",
    "                8 : 4 * (5 ** 7) - 4 * 5 * 5 * 5,\n",
    "                9 : 4 * (5 ** 8) - 4 * 5 * 5 * 5 * 3}\n",
    "        @lru_cache(None)\n",
    "        def count(i, flag1, flag2):\n",
    "            # flag1: 是否已经确定小于num\n",
    "            # flag2: 是否要求是回文数\n",
    "            if i == 0:\n",
    "                ref = {1: 1, 6: 9, 8: 8, 9: 6}\n",
    "            else:\n",
    "                ref = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}\n",
    "            if i == len(test):\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            if not flag2:\n",
    "                if flag1:\n",
    "                    for j in ref:\n",
    "                        cnt += count(i + 1, flag1, flag2)\n",
    "                else:\n",
    "                    for j in ref:\n",
    "                        if j < test[i]:\n",
    "                            cnt += count(i + 1, True, flag2)\n",
    "                        elif j == test[i]:\n",
    "                            cnt += count(i + 1, False, flag2)\n",
    "            else:\n",
    "                if i <= (len(test) - 1) // 2:\n",
    "                    if i == (len(test) - 1) // 2 and len(test) % 2 == 1:\n",
    "                        if flag1:\n",
    "                            for j in {0, 1, 8}:\n",
    "                                cnt += count(i + 1, flag1, flag2)\n",
    "                        else:\n",
    "                            for j in {0, 1, 8}:\n",
    "                                if j < test[i]:\n",
    "                                    cnt += count(i + 1, True, flag2)\n",
    "                                elif j == test[i]:\n",
    "                                    cnt += count(i + 1, False, flag2)\n",
    "                        return cnt\n",
    "                    if flag1:\n",
    "                        for j in ref:\n",
    "                            cnt += count(i + 1, flag1, flag2)\n",
    "                    else:\n",
    "                        for j in ref:\n",
    "                            if j < test[i]:\n",
    "                                cnt += count(i + 1, True, flag2)\n",
    "                            elif j == test[i]:\n",
    "                                cnt += count(i + 1, False, flag2)\n",
    "                else:\n",
    "                    if flag1:\n",
    "                        return 1\n",
    "                    else:\n",
    "                        x = ref[test[len(test) - 1 - i]]\n",
    "                        if x < test[i]:\n",
    "                            return 1\n",
    "                        elif x == test[i]:\n",
    "                            return count(i + 1, False, True)\n",
    "                        else:\n",
    "                            return 0\n",
    "            return cnt\n",
    "\n",
    "        ans = 0\n",
    "        ans += count(0, False, False)\n",
    "        ans -= count(0, False, True)\n",
    "        for i in range(1, len(num)):\n",
    "            ans += easy[i]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ind = {0:0, 1:1,6:9, 8:8, 9:6}\n",
    "pre = [0, 1, 6, 8, 9]\n",
    "res = pre[:]\n",
    "for _ in range(2, 10):\n",
    "    nex = []\n",
    "    for num in pre:\n",
    "        for d in ind:\n",
    "            nex.append(num*10+d)\n",
    "    res.extend(nex)\n",
    "    pre=  nex[:]\n",
    "res = sorted(set(res))\n",
    "def check(x):\n",
    "    if x <= 0:\n",
    "        return False\n",
    "    s = str(x)\n",
    "    t = int(\"\".join(str(ind[int(w)]) for w in s[::-1]))\n",
    "    return t != x\n",
    "\n",
    "res = [num for num in res if check(num)]\n",
    "res.append(1000000000)\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        return bisect.bisect_right(res, n) - bisect.bisect_left(res, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        mp = {0:0,1:1,8:8,6:9,9:6}\n",
    "        def reverse(i):\n",
    "            t = 0\n",
    "            while i:\n",
    "                t = t * 10 + mp[(i % 10)]\n",
    "                i //= 10\n",
    "            return t\n",
    "        # print(f'{reverse(81)}')\n",
    "        a = [0,1,6,8,9]\n",
    "        st = set()\n",
    "        def dfs(cur):\n",
    "            if cur > n:\n",
    "                return \n",
    "            if 1 <= cur <= n and reverse(cur) != cur:\n",
    "                st.add(cur)\n",
    "            for x in a:\n",
    "                if cur > 0: \n",
    "                    dfs(cur * 10 + x)\n",
    "                else:\n",
    "                    if x > 0:\n",
    "                        dfs(x)\n",
    "        dfs(0)\n",
    "        # print(f'{st}')\n",
    "        return len(st)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ind = dict()\n",
    "for a, b in zip(\"01689\", \"01986\"):\n",
    "    ind[a] = b\n",
    "pre = list(\"01689\")\n",
    "res = pre[:]\n",
    "for _ in range(2, 10):\n",
    "    nex = []\n",
    "    for s in pre:\n",
    "        for d in ind:\n",
    "            if s[0] != \"0\":\n",
    "                nex.append(s+d)\n",
    "    res.extend(nex)\n",
    "    pre = nex[:]\n",
    "\n",
    "\n",
    "def check(x):\n",
    "    if x <= 0:\n",
    "        return False\n",
    "    s = str(x)\n",
    "    t = int(\"\".join(str(ind[w]) for w in s[::-1]))\n",
    "    return t != x\n",
    "\n",
    "res = [num for num in set([int(num) for num in res]) if check(num)]\n",
    "res = sorted(res)\n",
    "res.append(10**9)\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        return bisect.bisect_right(res, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def confusingNumberII(self, n: int) -> int:\n",
    "        confuse_nums = [0, 1, 6, 8, 9]\n",
    "        dct = {\"0\": \"0\", \"1\": \"1\", \"6\": \"9\", \"8\": \"8\", \"9\": \"6\"}\n",
    "        s = str(n)\n",
    "\n",
    "        def check(st):\n",
    "            if int(st) != int(\"\".join(dct[t] for t in st)[::-1]):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def helper(i, pre, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num and check(pre))\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += helper(i + 1, \"\", False, False)\n",
    "            lower = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in confuse_nums:\n",
    "                if lower <= d <= up:\n",
    "                    res += helper(i+1, pre+str(d),is_limit and d == up, True)\n",
    "            return res\n",
    "        \n",
    "        return helper(0, \"\", True, False)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
